package com.kevin.Code.OfferReviewVersion2;

import scala.collection.mutable.HashMap$;

import java.util.*;

/**
 * @author Vinlee Xiao
 * @Classname EvaluateDivision
 * @Description Leetcode 399. 除法求值 同剑指Offer2 111 中等难度 图的算法
 * @Date 2022/1/14 22:04
 * @Version 1.0
 */
public class EvaluateDivision {

    /**
     * @param equations
     * @param values
     * @param queries
     * @return
     */
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {

        HashMap<String, HashMap<String, Double>> graph = buildGraph(equations, values);

        //定义一个结果数组 存储最终的结果
        double[] result = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            List<String> list = queries.get(i);
            String from = list.get(0);
            String to = list.get(1);
            //判断是否为
            if (!graph.containsKey(from) || !graph.containsKey(to)) {
                result[i] = -1.0;
            } else {
                //用于标记那些顶点被访问了
                HashSet<String> visited = new HashSet<>();
                double res = dfs(graph, from, to, visited);
                result[i] = res;
            }
        }

        return result;
    }

    /**
     * 建立节点到节点以及之间权值的映射
     *
     * @param equations
     * @param values
     * @return
     */
    private HashMap<String, HashMap<String, Double>> buildGraph(List<List<String>> equations, double[] values) {

        HashMap<String, HashMap<String, Double>> graph = new HashMap<>();

        int index = 0;
        for (List<String> list : equations) {
            String fromVertex = list.get(0);
            String toVertex = list.get(1);
            //u-v value
            graph.putIfAbsent(fromVertex, new HashMap<String, Double>());
            graph.get(fromVertex).put(toVertex, values[index]);

            graph.putIfAbsent(toVertex, new HashMap<String, Double>());
            graph.get(toVertex).putIfAbsent(fromVertex, 1.0 / values[index]);

            index++;
        }

        return graph;
    }

    /**
     * @param graph 顶点到顶点权重的映射
     * @param from  出度点
     * @param to    入度点
     *              //     * @param visited 已经被访问过的节点 避免陷入自环中
     * @return
     */
    private double dfs(HashMap<String, HashMap<String, Double>> graph, String from, String to, HashSet<String> visited) {

        //递归中止的条件
        if (from.equals(to)) {
            return 1.0;
        }
        //加入访问节点中
//        visited.add(from);
        HashMap<String, Double> neighbor = graph.get(from);
        for (Map.Entry<String, Double> entry : neighbor.entrySet()) {
            String next = entry.getKey();
            Double curQuotient = entry.getValue();
            //visited 的用法在此处不太理解

            double nextQuotient = dfs(graph, next, to, visited);
            if (nextQuotient > 0) {
                return curQuotient * nextQuotient;
            }

        }
        visited.remove(from);
        return -1.0;
    }

    public static void main(String[] args) {
        EvaluateDivision evaluateDivision = new EvaluateDivision();
        List<List<String>> equation = new ArrayList<>();
        List<String> list1 = new ArrayList<>();
        List<String> list2 = new ArrayList<>();
        list1.add("a");
        list1.add("b");
        equation.add(new ArrayList<>(list1));
        list2.add("b");
        list2.add("c");
        equation.add(new ArrayList<>(list2));
        double[] values = new double[]{2.0, 3.0};


//        evaluateDivision.calcEquation(equation, values);
    }

}
